Day 26: LeetCode Hard+Medium

LeetCode 212. Word Search II

Source

https://leetcode.com/problems/word-search-ii/

作法:

先clone Word Search的寫法，再稍作更動，並加速一下。

Level:Hard

技術支援

@JohnTing

加速法: 加上filter
如果word當中的character不在board裡，就不用找那個word了!

LeetCode 201. Bitwise AND of Numbers Range

Source

https://leetcode.com/problems/bitwise-and-of-numbers-range/

Discuss[1]

Observe

Ex: [5,8]

    101 <- len = 3
    110
&   111
   1000 <- len = 4
-------
   0000  
    
    

class Solution:
    def rangeBitwiseAnd(self, left: int, right: int) -> int:
        
        if len(bin(left)) != len(bin(right)):
            return 0
        for i in range(left+1,right+1):
            left = left & i
        return left    

YT[2]

Bitwise AND of Numbers Range

跟我一樣的疑惑!

Observe

Ex: [5,7]

idx 210
-------
    101
    110
&   111
-------
    100
    -    

作法

找出Out非1的位置，以[5,7]為例，則為index是2的情況，
index 2左邊(包含2)保留，index 2右邊捨棄。

以右移方式(/2)來找Out非1的位置，
右移直到m,n相同就停止，右移同時使用counter記錄移了幾次
PS: 右移 (>>1)
再由m左移counter(m/n<<counter)即所得。
PS: m/n == m或n

程式碼

class Solution:
    def rangeBitwiseAnd(self, left: int, right: int) -> int:
        '''
        >> -> /2
        << -> *2
           421
        ------         
        5: 101
        6: 110
        7: 111
        -------
           100
           OXX  O: the same X: diffirent
        可移掉右邊清為空留下左邊
        移掉右邊 -> 最後成00
        留下左邊 -> 不動
        
        op1: >> also means drop right bit
        do (>> 1) + counter until m == n
        
        op2: << counter
        '''
        
        cnt = 0
        while left!=right:
            left >>= 1
            right >>= 1
            cnt+=1
        return right << cnt    
            
        
        

Level:Medium